//
//  RangeBitwiseAnd.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/8/23.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  201. 数字范围按位与

import UIKit

/*
 201. 数字范围按位与
 
 给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

 示例 1:

 输入: [5,7]
 输出: 4
 示例 2:

 输入: [0,1]
 输出: 0
 */

class RangeBitwiseAnd: NSObject {
    //Brian Kernighan 算法
    
    /*
     Brian Kernighan 算法是一个位运算的算法，用于清除二进制最右边的1
     该算法的关键在于，当一个数 n 和 n-1 进行按位与运算后，起结果刚好等于 n 的二进制最右边的1变成0
     eg:   12   1  1  0  0
           11   1  0  1  1
     
     按位与  8   1  0  0  0
     
     可以发现 n 的最右边的1被转成了0
     
     基于上述技巧，我们可以用它来计算两个二进制字符串的公共前缀。

     其思想是，对于给定的范围[m,n]（m<n），我们可以对数字 n 迭代地应用上述技巧，清除最右边的1，直到它小于或等于 m，此时非公共前缀部分的 1 均被消去。因此最后我们返回 n 即可。
     
     */
    
    func rangeBitwiseAnd(_ m: Int, _ n: Int) -> Int {
        var n = n
        while m < n {
            //抹去最右边的 1
            n = n&(n-1)
        }
        return n
    }
}
